import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;
import java.util.concurrent.DelayQueue;

/**
 * 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
 *
 * 请你计算该表达式。返回一个表示表达式值的整数。
 * @param
 */
class Solution1 {
    Stack<Integer> stack=new Stack<>();
    public int evalRPN(String[] tokens) {
        for (String x:tokens){//遍历一遍数组，遇到括号入栈，遇到符号出栈
            if(!isOperatio(x)){//不是是符号,就放入
                stack.push(Integer.parseInt(x));//把string类型转换为int类型
            }else {//是符号
                //先出栈
                int num2=stack.pop();//第二个计算数据，先拿
                int num1=stack.pop();//第一个计算数据。后拿
                //结果入栈
                switch(x){//因为多种情况所以使用Switch语句
                    case "+":
                        stack.push(num1+num2);//放入
                        break;//记得break，不然继续执行
                    case "-":
                        stack.push(num1-num2);
                        break;
                    case"*":
                        stack.push(num1*num2);
                        break;
                    case "/":
                        stack.push(num1/num2);
                        break;
                }
            }
        }
        return stack.peek();//返回最后一个元素
    }
    public boolean isOperatio(String x){//判断是否为符号
        if(x.equals("+")||x.equals("-")||x.equals("*")||x.equals("/")){//因为是string，所以用””括起来
            return true;
        }
        return false;
    }
}


/**
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 */
class Solution2 {
    Stack<Character> stack=new Stack<>();
    public boolean isValid(String s) {
        for (int i = 0; i <s.length() ; i++) {
            char ch=s.charAt(i);//拿到对应下标char
            if(ch=='('||ch=='{'||ch=='['){//左括号，则入栈
                stack.push(ch);
            }else {//右括号
                if(stack.empty()){//当有右括号时栈为空，则不匹配
                    return false;
                }else {//栈不为空时
                    if ((ch=='}'&&stack.peek()=='{')||(ch==')'&&stack.peek()=='(')||(ch==']'&&stack.peek()=='[')){
                        stack.pop();//当匹配时则左括号出栈
                    }else {//不匹配情况则false
                        return false;
                    }
                }
            }
        }
        if(!stack.empty()){//最后看栈是否为空，当栈不为空时则代表左括号多了，因为右括号已经走完，但是左括号还有
            return false;
        }
        //只有当左右都为空是才是匹配的情况
        return true;

    }
}
/**
 * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。
 * 例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
 */
/*class Solution3 {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Deque


    }
}*/

